#coding=utf-8 
'''
Created on 2012-10-26

@author: infear
'''
#http://blog.csdn.net/v_JULY_v/article/details/6057286
#76.复杂链表的复制（链表、算法）
#题目：有一个复杂链表，其结点除了有一个m_pNext指针指向下一个结点外，
#还有一个m_pSibling指向链表中的任一结点或者NULL。其结点的C++定义如下：
# struct ComplexNode
#{
#    int m_nValue;
#    ComplexNode* m_pNext;
#    ComplexNode* m_pSibling;
#};
class Complexnode():
    def __init__(self,__next,__sibling,__value):
        self.next=__next
        self.sibling=__sibling
        self.value=__value
    
    def copy(self):
        p1=self
        if not p1:
            return None
        while p1:
            a=Complexnode(None,None,p1.value)
            a.next=p1.next
            p1.next=a
            a.sibling=p1
            p1=a.next
        p1=self
        result=p1.next
        while p1:
            a=p1.next
            if p1.sibling:
                a.sibling=p1.sibling.next
            else:
                a.sibling=None
            p1=p1.next.next
        p1=self
        while p1:
            a=p1.next
            p1.next=a.next
            if a.next:
                a.next=a.next.next
            p1=p1.next
        return result
    
    def _print(self):
        p1=self
        while p1:
            print p1.value
            p1=p1.next
        p1=self
        while p1:
            if p1.sibling:
                print p1.sibling.value
            else:
                print ""
            p1=p1.next
#test 76
#a=Complexnode(None,None,"a")
#b=Complexnode(None,None,"b")
#c=Complexnode(None,None,"c")
#d=Complexnode(None,None,"d")
#e=Complexnode(None,None,"e")
#a.next=b
#b.next=c
#c.next=d
#d.next=e
#a.sibling=c
#d.sibling=b
#b.sibling=e
#a._print()
#copy_a=a.copy()
#copy_a._print()

#81
#81.第1组百度面试题
#1.一个int数组，里面数据无任何限制，要求求出所有这样的数a[i]，
#其左边的数都小于等于它，右边的数都大于等于它。
#能否只用一个额外数组和少量其它空间实现。
def findRightPosIndex(arr):
    l=len(arr)-1
    min_arr=[]
    i=l
    min=arr[i]
    while i!=-1:
        if arr[i]<min:
            min=arr[i]
        min_arr.insert(0,min)
        i=i-1
    max_arr=[]
    i=0
    max=arr[i]
    while i!=l+1:
        if arr[i]>max:
            max=arr[i]
        max_arr.append(max)
        i=i+1
    while i!=0:
        i=i-1
        if arr[i]<=min_arr[i] and arr[i]>=max_arr[i]:
            yield arr[i]

#优化的地方在于不是用一个数组来存放第i个元素左边所有值的最大值，而是只有一个一个max变量（min也类似 ），一个额外的数组是用来存放结果的
#对于同时通过max和min测试的元素才会置1
def findRightPosIndexOptimize(arr):
    if not arr or len(arr)==0:
        return 0
    l=len(arr)
    max_min=[0]*l
    result=[]
    p=0
    max=arr[0]
    while p!=l:
        if max<=arr[p]:
            max=arr[p]
            max_min[p]=1
        p=p+1
    min=arr[l-1]
    while p!=0:
        p=p-1
        if min>=arr[p]:
            min=arr[p]
        else:
            max_min[p]=0
    return max_min  
                    
print list(findRightPosIndexOptimize([1,2,4,3,5,6]))
    